package com.learn.algorithm;

import java.util.Arrays;

/**
 * 冒泡排序 (和邻居比)
 * 原理：把相邻的元素两两比较，根据大小来交换元素的位置。
 * 复杂度是 O(N^2)
 */
public class BubbleSort {
    public static void main(String[] args) {
        //int[] array = new int[]{5,8,6,3,9,2,1,7};
        int[] array = new int[]{3,4,2,1,5,6,7,8};
        sort(array);
        System.out.println(Arrays.toString(array));
    }
    //比大小排序-原始排序
    private static void sortOld(int array[]) {
        int tmp = 0;
        // 外部循环控制所有的回合，
        // 内部循环代表每一轮的冒泡处理
        // 先进行元素比较，再进行元素交换
        for (int i=0;i<array.length;i++){
            for(int j = 0;j<array.length-i-1;j++) {
                if (array[j] > array[j+1]) {
                    //换位
                    tmp= array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                }
            }
        }
    }

    private static void sort(int[] array) {
        int tmp = 0;
        //记录最后一次交换的位置
        int lastExchangeIndex = 0;
        //无序数列的边界，每次比较只需要比到这里为止
        int sortBorder = array.length - 1;

        for(int i=0;i<array.length;i++){
            //有序标记，每一轮的初始是true
            boolean isSorted = true;
            for(int j = 0;j<sortBorder;j++) {
                if (array[j] > array[j+1]) {
                    //换位
                    tmp= array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                    //有元素交换，所以不是有序，标记变为false
                    isSorted = false;
                    //把无序数列的边界更新为最后一次交换元素的位置
                    lastExchangeIndex = j;
                }
            }
            sortBorder = lastExchangeIndex;
            if (isSorted) {
                break;
            }
        }
    }
}
